import functools


class Solution(object):
    def uniquePathsIII(self, grid):
        m = len(grid)
        n = len(grid[0])
        start = -1
        end = -1
        available = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] >= 0:
                    available.add(i * n + j)
                    if grid[i][j] == 1:
                        start = i * n + j
                    if grid[i][j] == 2:
                        end = i * n + j
        if start == -1 or end == -1:
            return 0
        target = 0
        for node in available:
            if node != end:
                target |= (1 << node)
        @functools.cache
        def dfs(val, node):
            if val == 0:
                if node == start:
                    return 1
                else:
                    return 0
            x, y = node // n, node % n
            now_ans = 0
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < m and 0 <= uy < n and (val >> (ux * n + uy)) & 1:
                    last_val = val ^ (1 << (ux * n + uy))
                    now_ans += dfs(last_val, ux * n + uy)
            return now_ans

        return dfs(target, end)


data = Solution()
grid = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 2, -1]]
print(data.uniquePathsIII(grid))
grid = [[1, 0], [2, 0]]
print(data.uniquePathsIII(grid))
